package com.company.test27_28;

import java.util.List;

/**
 * Created by Administrator on 2016.11.8.
 */
public interface Graph<V> {
    //获取图的所有端点的总数
    public int getSize();

    //获取图中所有的端点
    public List<V> getVertices();

    //获取图中的一个端点
    public V getVertex(int index);

    //输入一个端点，获取该端点的编号
    public int getIndex(V v);

    //获取一个端点的邻居
    public List<Integer> getNeighbors(int index);

    public List<Integer> getHamiltonianPath(V v);

    //获取一个点的度
    public int getDegree(int v);

    //获取邻接矩阵
    public int[][] getAdjacencyMatrix();

    //输出邻接矩阵
    public void printAdjacencyMatrix();

    //输出所有的边
    public void printEdges();

    //深度优先搜索
    public SpanningTree dfs(int v);

    //广度优先搜索
    public SpanningTree bfs(int v);

    //判断该图是否为二部图
    public boolean isBipartite();

    //增加一个点
    public boolean add(V vertex);

    //删除一个点
    public boolean remove(V vertex);

    //增加一条边
    public boolean add(Edge edge);

    //移去一条边
    public boolean remove(Edge edge);

    interface Edge{
        int getU();
        int getV();
    };

    public static Graph maxInducedSubgraph(Graph edge, int k){
        boolean z=true;

        while (z){
            z=false;
            for(int i=0;i<edge.getSize();i++){
                if(edge.getDegree(i)<k) {
                    edge.remove(edge.getVertex(i));
                    z=true;
                }
            }
        }
        return edge;
    }

    interface SpanningTree<V>{
        int getRoot();

        int getParent(int v);

        List<Integer> getSearchOrders();

        int getNumberOfVerticesFound();

        List<V> getPath(int index);

        void printPath(int index);

        void printTree();
    }
}